0
0.0

Jun 29, 2018
06/18

by
Jérémy Barbay

texts

######
eye 0

######
favorite 0

######
comment 0

We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+\lg \alpha))\subseteq O(n\lg n)$, where the alternation $\alpha\in[1..n-1]$ measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size $n$ and alternation $\alpha$. Such results refine the state of the art...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1602.00023

116
116

May 24, 2016
05/16

by
Pierre Barbay

texts

######
eye 116

######
favorite 0

######
comment 0

Topic: bub_upload

Source: http://books.google.com/books?id=YDw3moTmBhsC&hl=&source=gbs_api

0
0.0

Jun 29, 2018
06/18

by
Jérémy Barbay

texts

######
eye 0

######
favorite 0

######
comment 0

The problem of the Hanoi Tower is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound are the solution of a simple recursive function (the solution is so easy that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some very minor changes in the rules of the Hanoi Tower yield various increases of complexity in the solution, so that they require a deeper...

Topics: General Literature, Computing Research Repository

Source: http://arxiv.org/abs/1602.03934

93
93

Sep 21, 2013
09/13

by
Jérémy Barbay

texts

######
eye 93

######
favorite 0

######
comment 0

We describe an algorithm computing an optimal prefix free code from $N$ unsorted positive integer weights in time linear in the number of machine words holding those weights. This algorithm takes advantage of common non-algebraic instructions, and of specific results on optimal prefix free codes. This result improves over the state of the art complexities of $O(N\lg N)$ in the algebraic decision tree model and $O(N\lg\lg N)$ in the RAM model for the computation of Huffman's codes, a landmark in...

Source: http://arxiv.org/abs/1204.5801v3

0
0.0

Jun 30, 2018
06/18

by
Jérémy Barbay; Carlos Ochoa

texts

######
eye 0

######
favorite 0

######
comment 0

Refinements of the worst case complexity over instances of fixed input size consider the input order or the input structure, but rarely both at the same time. Barbay et al. [2016] described ``synergistic'' solutions on multisets, which take advantage of the input order and the input structure, such as to asymptotically outperform any comparable solution which takes advantage only of one of those features. We consider the extension of their results to the computation of the \textsc{Maxima Set}...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1702.08545

31
31

Sep 21, 2013
09/13

by
Jérémy Barbay; Gonzalo Navarro

texts

######
eye 31

######
favorite 0

######
comment 0

We explore various techniques to compress a permutation $\pi$ over n integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi$(i) and the application of its inverse $\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $\pi^k(i)$ of it, of integer...

Source: http://arxiv.org/abs/0902.1038v1

44
44

Sep 19, 2013
09/13

by
Jérémy Barbay; Johannes Fischer

texts

######
eye 44

######
favorite 0

######
comment 0

LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks, and to express the relative position of the first element of each block within a previous block. They were used to encode ordinal trees and to index integer arrays in order to support range minimum queries on them. We describe how they yield many other convenient results in a variety of areas, from data structures to algorithms: some compressed succinct indices for range minimum queries; a new...

Source: http://arxiv.org/abs/1009.5863v1

36
36

Sep 21, 2013
09/13

by
Jérémy Barbay; Gonzalo Navarro

texts

######
eye 36

######
favorite 0

######
comment 0

Previous compact representations of permutations have focused on adding a small index on top of the plain data $ $, in order to efficiently support the application of the inverse or the iterated permutation. In this paper we initiate the study of techniques that exploit the compressibility of the data itself, while retaining efficient computation of $\pi(i)$ and its inverse. In particular, we focus on exploiting {\em runs}, which are subsets (contiguous or not) of the domain where the...

Source: http://arxiv.org/abs/1108.4408v1

2
2.0

Jun 30, 2018
06/18

by
Jérémy Barbay; Javiel Rojas

texts

######
eye 2

######
favorite 0

######
comment 0

We study the problem of computing the \textsc{Maxima} of a set of $n$ $d$-dimensional points. For dimensions 2 and 3, there are algorithms to solve the problem with order-oblivious instance-optimal running time. However, in higher dimensions there is still room for improvements. We present an algorithm sensitive to the structural entropy of the input set, which improves the running time, for large classes of instances, on the best solution for \textsc{Maxima} to date for $d \ge 4$.

Topics: Computational Geometry, Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1701.03693

5
5.0

Jun 27, 2018
06/18

by
Jérémy Barbay; Pablo Pérez-Lantero

texts

######
eye 5

######
favorite 0

######
comment 0

The Swap-Insert Correction distance from a string $S$ of length $n$ to another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting $S$ into $L$. Contrarily to other correction distances, computing it is NP-Hard in the size $d$ of the alphabet. We describe an algorithm computing this distance in time within $O(d^2 nm g^{d-1})$, where there are $n_\alpha$ occurrences of $\alpha$ in $S$, $m_\alpha$...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1504.07298

67
67

Sep 21, 2013
09/13

by
J. Barbay; G. Navarro; P. Pérez-Lantero

texts

######
eye 67

######
favorite 0

######
comment 0

Given a set $P$ of $n$ planar points, two axes and a real-valued score function $f()$ on subsets of $P$, the Optimal Planar Box problem consists in finding a box (i.e. axis-aligned rectangle) $H$ maximizing $f(H\cap P)$. We consider the case where $f()$ is monotone decomposable, i.e. there exists a composition function $g()$ monotone in its two arguments such that $f(A)=g(f(A_1),f(A_2))$ for every subset $A\subseteq P$ and every partition $\{A_1,A_2\}$ of $A$. In this context we propose a...

Source: http://arxiv.org/abs/1204.2034v1

0
0.0

Jun 29, 2018
06/18

by
Jérémy Barbay; Carlos Ochoa; Srinivasa Rao Satti

texts

######
eye 0

######
favorite 0

######
comment 0

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size $n$ and number of queries $q$ fixed (i.e., the query size). Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1608.06666

8
8.0

Jun 27, 2018
06/18

by
Peyman Afshani; Jérémy Barbay; Timothy Chan

texts

######
eye 8

######
favorite 0

######
comment 0

We prove the existence of an algorithm $A$ for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every sequence $\sigma$ of $n$ points and for every algorithm $A'$ in a certain class $\mathcal{A}$, the running time of $A$ on input $\sigma$ is at most a constant factor times the maximum running time of $A'$ on the worst possible permutation of $\sigma$ for $A'$. We establish a stronger property: for every sequence $\sigma$ of points and every...

Topics: Computational Geometry, Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1505.00184

8
8.0

Jun 27, 2018
06/18

by
Jeremy Barbay; Carlos Ochoa; Pablo Perez-Lantero

texts

######
eye 8

######
favorite 0

######
comment 0

Divide-and-conquer is a central paradigm for the design of algorithms, through which some fundamental computational problems, such as sorting arrays and computing convex hulls, are solved in optimal time within $\Theta(n\log{n})$ in the worst case over instances of size $n$. A finer analysis of those problems yields complexities within $O(n(1 + \mathcal{H}(n_1, \dots, n_k))) \subseteq O(n(1{+}\log{k})) \subseteq O(n\log{n})$ in the worst case over all instances of size $n$ composed of $k$...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1505.02820

200
200

Jul 21, 2010
07/10

by
Viswanathan, R.; Barbay, G.; Stevens, N. J

texts

######
eye 200

######
favorite 0

######
comment 0

The Hughes SCREENS (Space Craft Response to Environments of Space) technique was applied to generic spin and 3-axis stabilized spacecraft models. It involved the NASCAP modeling for surface charging and lumped element modeling for transients coupling into a spacecraft. A differential voltage between antenna and spun shelf of approx. 400 V and current of 12 A resulted from discharge at antenna for the spinner and approx. 3 kv and 0.3 A from a discharge at solar panels for the 3-axis stabilized...

Topics: MISSION PLANNING, OCCULTATION, ORBITAL MECHANICS, SUN, ASTRONOMICAL CATALOGS, EPHEMERIDES, SIDEREAL...

36
36

Sep 18, 2013
09/13

by
Jérémy Barbay; Francisco Claude; Gonzalo Navarro

texts

######
eye 36

######
favorite 0

######
comment 0

Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations,...

Source: http://arxiv.org/abs/1201.3602v1

0
0.0

Jun 27, 2018
06/18

by
Jérémy Barbay; Pablo Pérez-Lantero; Javiel Rojas-Ledesma

texts

######
eye 0

######
favorite 0

######
comment 0

The KLEE'S MESURE of $n$ axis-parallel boxes in $\mathbb{R}^d$ is the volume of their union. It can be computed in time within $O(n^{d/2})$ in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size $h$, and yields a solution running in time within...

Topics: Computing Research Repository, Data Structures and Algorithms

Source: http://arxiv.org/abs/1505.02855

46
46

Sep 18, 2013
09/13

by
S. Barbay; G. Giacomelli; S. Lepri; A. Zavatta

texts

######
eye 46

######
favorite 0

######
comment 0

We report the experimental evidence of noise-induced phase synchronization in a vertical cavity laser. The polarized laser emission is entrained with the input periodic pump modulation when an optimal amount of white, gaussian noise is applied. We characterize the phenomenon, evaluating the average frequency of the output signal and the diffusion coefficient of the phase difference variable. Their values are roughly independent on different waveforms of periodic input, provided that a simple...

Source: http://arxiv.org/abs/cond-mat/0303084v2

0
0.0

Jun 28, 2018
06/18

by
F Selmi; S Coulibaly; Z Loghmari; Isabelle Sagnes; Gregoire Beaudoin; Marcel G. Clerc; Sylvain Barbay

texts

######
eye 0

######
favorite 0

######
comment 0

Extreme events such as rogue wave in optics and fluids are often associated with the merging dynamics of coherent structures. We present experimental and numerical results on the physics of extreme events appearance in a spatially extended semiconductor microcavity laser with intracavity saturable absorber. This system can display deterministic irregular dynamics only thanks to spatial coupling through diffraction of light. We have identified parameter regions where extreme events are...

Topics: Chaotic Dynamics, Nonlinear Sciences

Source: http://arxiv.org/abs/1511.08045

34
34

Oct 23, 2014
10/14

by
Nair, K Saidas; Barbay, Jessica; Smith, Richard S; Masli, Sharmila; John, Simon WM

texts

######
eye 34

######
favorite 0

######
comment 0

This article is from BMC Genetics , volume 15 . Abstract Background: The molecular mechanisms causing pigment dispersion syndrome (PDS) and the pathway(s) by which it progresses to pigmentary glaucoma are not known. Mutations in two melanosomal protein genes (Tyrp1b and GpnmbR150X) are responsible for pigment dispersing iris disease, which progresses to intraocular pressure (IOP) elevation and subsequent glaucoma in DBA/2J mice. Melanosomal defects along with ocular immune abnormalities play a...

Source: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3974199

39
39

Sep 22, 2013
09/13

by
Remy Braive; Sylvain Barbay; Isabelle Sagnes; Audrey Miard; Isabelle Robert-Philip; Alexios Beveratos

texts

######
eye 39

######
favorite 0

######
comment 0

We report on a series of experiments on the dynamics of spontaneous emission controlled nanolasers. The laser cavity is a photonic crystal slab cavity, embedding self-assembled quantum dots as gain material. The implementation of cavity electrodynamics effects increases significantly the large signal modulation bandwidth, with measured modulation speeds of the order of 10 GHz while keeping an extinction ratio of 19 dB. A linear transient wavelength shift is reported, corresponding to a chirp of...

Source: http://arxiv.org/abs/0812.1693v1

0
0.0

Jun 28, 2018
06/18

by
F Selmi; R Braive; G Beaudoin; I Sagnes; R Kuszelewicz; Sylvain Barbay

texts

######
eye 0

######
favorite 0

######
comment 0

Neuromimetic systems are systems mimicking the functionalities orarchitecture of biological neurons and may present an alternativepath for efficient computing and information processing. We demonstratehere experimentally temporal summation in a neuromimetic micropillarlaser with integrated saturable absorber. Temporal summation is theproperty of neurons to integrate delayed input stimuli and to respondby an all-or-none kind of response if the inputs arrive in a sufficientlysmall time window....

Topics: Physics, Optics, Chaotic Dynamics, Nonlinear Sciences

Source: http://arxiv.org/abs/1510.07853

30
30

Sep 18, 2013
09/13

by
Daniele Bajoni. Elizaveta Semenova; Aristide Lemaître; Sophie Bouchoule; Esther Wertz; Pascale Senellart; Sylvain Barbay; Robert Kuszelewicz; Jacqueline Bloch

texts

######
eye 30

######
favorite 0

######
comment 0

We report on a new type of optical nonlinearity in a polariton p-i-n microcavity. Abrupt switching between the strong and weak coupling regime is induced by controlling the electric field within the cavity. As a consequence bistable cycles are observed for low optical powers (2-3 orders of magnitude less than for Kerr induced bistability). Signatures of switching fronts propagating through the whole 300 microns x 300 microns mesa surface are evidenced.

Source: http://arxiv.org/abs/0809.4758v1